package 剑指offer.数组;

/**
 * TODO
 * 输入一个数组，检查里面有多少逆序对
 * 例如：7,6,5 有三组逆序对：76,75,65 这三组
 */
public class 第51题数组中的逆序对 {

    static int cnt;

    /**
     * 解法：按照归并排序，先将数组分解成一个个的单个元素
     * 然后每两个比较一次，统计逆序个数。
     * 单个合并完后，会得到两个一组的新组合，然后设置两根指向这两个数组尾巴的指针
     * 比较大小，若前面的指针大于后面的指针，说明前面指针指向的这个数大于后面数组里面的全部数据，
     * 此时统计新的逆序对数，且把前面指针指向的这个较大的数存入排序数组中，并向前移动前指针，然后再比较
     *
     * 若比较的过程中发现前面的小于后面的，则把后面的指针往前移动，再比较
     *
     * 反正一旦遇到前指针大于后指针的情况，就计数，并把前指针指向的数存入到排序数组中
     * @param array
     * @return
     */
    public static int InversePairs(int[] array) {
        cnt = 0;
        if (array != null)
            mergeSortUp2Down(array, 0, array.length - 1);
        return cnt;
    }

    /*
     * 归并排序(从上往下)
     */
    public static void mergeSortUp2Down(int[] a, int start, int end) {
        if (start >= end)
            return;
        int mid = (start + end) >> 1;

        mergeSortUp2Down(a, start, mid);
        mergeSortUp2Down(a, mid + 1, end);

        merge(a, start, mid, end);
    }

    /*
     * 将一个数组中的两个相邻有序区间合并成一个
     */
    public static void merge(int[] a, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1];

        // i
        int i = start;
        int j = mid + 1;
        int k = 0;
        // 防止越界
        while (i <= mid && j <= end) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else {
                tmp[k++] = a[j++];
                // 计数器累加的时候，应该加上的是：当前这个指针要往前面移动的数字移动的次数
                cnt += mid - i + 1;
                cnt %= 1000000007;
            }
        }
        // 把剩余本来有序的数据添加到临时数组
        while (i <= mid)
            tmp[k++] = a[i++];
        while (j <= end)
            tmp[k++] = a[j++];
        // 然后把排好序的临时数组覆盖原始无序数组
        for (k = 0; k < tmp.length; k++)
            a[start + k] = tmp[k];
    }

    public static void main(String[] args) {
        int[] array = {6, 3, 7, 2};
        System.out.println(InversePairs(array));
    }
}
